package leetcode101.mathematical_problem;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code13
 * @Description 462. 最少移动次数使数组元素相等 II
 * 给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
 *
 * 例如:
 *
 * 输入:
 * [1,2,3]
 *
 * 输出:
 * 2
 *
 * 说明：
 * 只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：
 *
 * [1,2,3]  =>  [2,2,3]  =>  [2,2,2]
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-27 9:56
 */
public class Code13 {

    public static void main(String[] args) {

    }

    public static int minMoves2(int[] nums) {
        int sum = 0;
        int median = quickSelect(nums, 0, nums.length - 1, nums.length / 2);

        for (int num : nums) {
            sum += Math.abs(median - num);
        }
        return sum;
    }

    public static int quickSelect(int[] arr, int low, int high, int k) {
        if (low < high) {
            int pivot = partition(arr, low ,high);
            if (pivot > k) {
                return quickSelect(arr, low, pivot - 1, k);
            } else if (pivot < k) {
                return quickSelect(arr, pivot + 1, high, k);
            } else {
                return arr[k];
            }
        } else {
            return arr[low];
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int temp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= temp) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= temp) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = temp;
        return low;
    }
}
